class Solution {
public:   
    int getSum(vector<int>& nums,int s,int k){
        if(s == 0){
            return nums[s+k-1];
        }
        return nums[s+k-1] - nums[s-1];
    }            
                                        
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 1;i < n;i++){
            nums[i] += nums[i-1];
        }
        
        vector<vector<int>> dp(n-k+1,vector<int>(4));
        
        for(int i = 0;i <= n-k;i++){
            for(int j = 1;j <= 3;j++){
                if(i == 0){
                    dp[i][j] = getSum(nums,i,k);
                }else if(i < k){
                    dp[i][j] = max(dp[i-1][j],getSum(nums,i,k));
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i-k][j-1]+getSum(nums,i,k));
                }
            }
        }
        
        vector<int> ret(3);
        int j = 3;
        int i = n-k;
        while(j >= 1){
            if(i == 0){
                ret[0] = i;
                break;
            }else if(dp[i-1][j] == dp[i][j]){
                i--;
            }else{
                ret[j-1] = i;
                j--;
                i -= k;
            }
        }
        
        return ret;
    }
};
